package com.briup.day27.collections;

public class MyLinkedList implements MyList {

	// 链表中只需要保存一个头节点，即可间接访问到整个链式结构中的所有节点
	private Node first;

	// 记录集合中保存元素的个数
	private int size;

	// 节点内部类
	public static class Node {
		public Object data; // 节点中保存的数据
		public Node next; // 下一个节点的引用

		public Node(Object data) {
			this.data = data;
		}
	}

	@Override
	public boolean add(Object o) {
		// 无论节点如何插入，新的节点对象一定是要创建的
		Node node = new Node(o);

		if (first == null) {
			// 如果是第一次向链表中插入数据，让它充当头节点
			first = node;
		} else {
			// 如果不是第一次向链表中插入数据，
			// 需要找到当前链表的尾节点，
			// 让尾节点指向新节点，让新节点充当新的尾节点
			Node n = first;
			while (n.next != null)
				n = n.next;

			// 当while循环结束之后，n就是尾节点了
			n.next = node;
		}
		size++;
		return true;
	}

	@Override
	public void clear() {
		// 遍历链表，释放每两个节点之间的关联关系
		Node n = first;
		while (n != null) {
			// 如果在这里直接把n.next设为空，就无法继续遍历接下来的节点
			// 所以必须临时存储一下n的下一个节点引用
			// 把n的下一个节点设为空之后，再把刚才保存的引用赋值给n
			Node next = n.next;

			n.next = null;
			n.data = null;

			n = next;
		}

		// 重置头节点
		first = null;
	}

	@Override
	public boolean contains(Object o) {
		Node n = first;
		if (o == null) {
			while (n != null) {
				if (n.data == null)
					return true;
				n = n.next;
			}
		} else {
			while (n != null) {
				if (o.equals(n.data))
					return true;
				n = n.next;
			}
		}
		return false;
	}

	@Override
	public boolean isEmpty() {
		return first == null;
	}

	@Override
	public boolean remove(Object o) {

		// 如果链表中没有节点，则直接返回false
		if (first == null)
			return false;

		// 思路：
		// 先要通过遍历找到要删除的元素存在哪个节点中
		// 让这个节点的上一个节点指向它的下一个节点
		Node n = first; // 当前节点
		Node b = null; // 上一个节点

		if (o == null) {
			if (o == n.data) {
				removeFirst();
				return true;
			}
			while (n != null) {
				if (n.data == null) {
					unlink(b, n);
					return true;
				}
				b = n; // 把当前节点赋值给上一个节点
				n = n.next; // 把下一个节点赋值给当前节点
			}
		} else {
			// 先判断要删除的元素是否是头节点中的元素
			if (o.equals(n.data)) {
				removeFirst();
				return true;
			}
			while (n != null) {
				if (o.equals(n.data)) {
					unlink(b, n);
					return true;
				}
				b = n;
				n = n.next;
			}
		}
		return false;
	}

	// 删除非头节点
	private void unlink(Node before, Node curr) {
		// 先临时保存下一个节点的地址
		Node next = curr.next;
		// 把被删节点的data和next属性都清空
		curr.data = null;
		curr.next = null;
		// 把上一个节点指向下一个节点
		before.next = next;
		size--;
	}

	// 删除头节点
	private void removeFirst() {
		// 先临时保存第二个节点的地址
		Node second = first.next;
		// 把前两个节点的关联释放，清空头节点中保存的数据
		first.data = null;
		first.next = null;
		// 让刚才保存好的第二个节点充当新的头节点
		first = second;
		size--;
	}

	@Override
	public int size() {
		return size;
	}

	@Override
	public Object[] toArray() {
		// 创建一个数组
		Object[] arr = new Object[size];

		Node n = first;
		// 遍历数组，每次放入一个元素
		for (int i = 0; i < arr.length; i++) {
			arr[i] = n.data;
			n = n.next;
		}
		return arr;
	}

	@Override
	public MyIterator iterator() {
		return new MyItr();
	}

	private class MyItr implements MyIterator {
		private Node curr = first;

		@Override
		public boolean hasNext() {
			return curr != null;
		}

		@Override
		public Object next() {
			Object data = curr.data;
			curr = curr.next;
			return data;
		}
	}

	
	// 向链表中指定位置插入一个元素
	@Override
	public void add(int index, Object o) {
		if (index < 0 || index > size) {
			System.out.println("索引值不合法，插入失败！");
			return;
		}
		
		// 思路：插入到index位置，就代表要替换掉原有的index位置上的节点
		// 让原来index位置上的节点变成第index + 1个节点 
		// 假设index位置上的节点为n，index - 1位置上的节点为b
		// 新节点为node
		// b.next = node;  node.next = n;
		
		// 因为单向链表中寻找前一个节点不太方便，所以可以做如下调整：
		// 假设index - 1位置上的元素为b
		// b.next = node;  node.next = b.next;
		
		// 创建一个新的节点
		Node node = new Node(o);
		
		// 对于插入头节点进行特殊处理
		if (index == 0) {
			// 直接让新节点指向头节点
			node.next = first;
			// 让新节点充当新的头节点
			first = node;
			size++;
			return;
		}
		
		// 找index - 1位置上的节点
		Node b = first;
		for (int i = 0; i < index - 1; i++) 
			b = b.next;
		
		// 临时保存b当前的下一个节点
		Node next = b.next;
		// 让前一个节点指向新节点
		b.next = node;
		// node指向原来b.next
		node.next = next;
		size++;
	}

	@Override
	public Object get(int index) {
		Node n = first;
		for (int i = 0; i < index; i++) 
			n = n.next;
		return n.data;
	}

	// 删除链表中某个指定位置的元素，返回值是被删掉的元素
	@Override
	public Object remove(int index) {
		if (index < 0 || index >= size) {
			System.out.println("索引值不合法，删除失败！");
			return null;
		}
		
		// 删除头节点特殊处理
		if (index == 0) {
			Node second = first.next;
			Object obj = first.data;
			first.data = null;
			first.next = null;
			// 让原来的第二个节点充当新的头节点
			first = second;
			size--;
			return obj;
		}
		
		// 需要让index - 1节点的next直接指向index + 1
		Node b = first;
		for (int i = 0; i < index - 1; i++) 
			b = b.next;
		
		// b=before 被删除的前一个节点
		// c=current 被删除的节点
		// n=next 被删除的下一个节点
		Node c = b.next;
		Node n = c.next;
		
		// 先把被删节点中的元素取出，用于方法的返回
		Object obj = c.data;
		// 断开被删节点和它指向的后一个节点的关联
		// 并清空它保存的元素
		c.next = null;
		c.data = null;
		// 让前一个节点指向后一个节点
		b.next = n;
		
		size--;
		return obj;
	}

	@Override
	public Object set(int index, Object o) {
		Node n = first;
		for (int i = 0; i < index; i++) 
			n = n.next;
		
		Object obj = n.data;
		n.data = o;
		return obj;
	}

}
